def is_valid(s: str) -> bool:

    # 定义一个字典，将每个右括号映射到对应的左括号，用于匹配
    dic = {')': '(', ']': '[', '}': '{'}
    # 初始化一个空的堆栈，用于存放左括号
    stack = []

    # 遍历字符串中的每个字符
    for i in s:
        # 如果堆栈不为空且当前字符是右括号（存在于字典的键中）
        if stack and i in dic:
            # 判断堆栈顶部的元素是否是当前右括号对应的左括号
            if stack[-1] == dic[i]:
                # 如果匹配成功，弹出堆栈顶部的元素（已经匹配到一对括号）
                stack.pop()
            else:
                # 如果不匹配，立即返回False，表示括号不配对
                return False
        else:
            # 当前字符是左括号（或堆栈为空时遇到任何字符）
            # 将左括号压入堆栈，用于后续匹配
            stack.append(i)

    # 最后判断堆栈是否为空
    # 如果为空，说明所有括号都正确匹配
    # 如果不为空，说明存在未匹配的左括号
    return not stack


if __name__ == '__main__':
    # print(is_valid('()[]'))
    # print(is_valid('[()]'))
    print(is_valid('[(])'))






'''
复杂度分析
时间复杂度：O(N)。遍历了一遍字符串。
空间复杂度：O(N)。最坏情况下，假如输入是 (((((((，栈的大小将是输入字符串的长度。
'''